#include <vector>
#include <iostream>
#include <unordered_map>
using namespace std;
class Solution
{
public:
    int subarraySum(vector<int> &nums, int k)
    {
        vector<int> add(nums.size() + 1);
        // add[0]=nums[-]+...+nums[-1]==0
        unordered_map<int, int> u_map{{0, 1}};
        for (int i = 1; i < add.size(); i++)
        {
            add[i] = nums[i - 1] + add[i - 1];
        }
        // 从后往前找
        int res = 0;
        for (int i = 1; i < add.size(); i++)
        {
            // 前面如果出现过 add[j]==add[i]-k
            // 则表明 add[i]-arr[j]==k
            // 所以 nums[j-1]+...+num[i-1]==k(符合题意)
            res += u_map[add[i] - k];
            u_map[add[i]]++;
        }
        return res;
    }
};